// m

// 给定一个只包含0、1元素的二维数组，1代表岛屿，0代表水，一座岛的面积就是上下左右相邻的1所组成的连通块的数目
// 计算最大的岛屿面积

// 解题思路
// 思路1： 深度优先搜索
// 1.遍历二维数组中的每一个元素，对于每个值为1的元素：
//    1. 将该位置上的值置位0（防止二次重复计算）
//    2. 递归搜索该位置上下左右四个位置，并统计搜到值为1的元素个数
//    3. 返回值为1的元素个数（即为该岛的面积）
// 2. 维护并更新最大的岛屿面积
// 3. 返回最大的岛面积

// 复杂度分析
// 时间复杂度：O(m * n)， m和n分别为行数和列数
// 空间复杂度：O(m * n)

function maxAreaOfIsland(grid) {
    function dfs(grid, i, j) {
        let n = grid.length
        let m = grid[0].length
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] === 0) {
            return 0
        }
        let ans = 1
        grid[i][j] = 0
        ans += dfs(grid, i + 1, j)
        ans += dfs(grid, i, j + 1)
        ans += dfs(grid, i - 1, j)
        ans += dfs(grid, i, j - 1)
        return ans
    }
    let ans = 0
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 1) {
                ans = Math.max(ans, dfs(grid, i, j))
            }
        }
    }
    return ans
}